package leetcode.每日一题;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/12/29 11:53
 * @description：https://leetcode-cn.com/problems/count-special-quadruplets/
 */
public class 统计特殊四元组 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.countQuadruplets(new int[]{1, 1, 1, 3, 5}));
    }

    class Solution {
        // 直接枚举
        /*public int countQuadruplets(int[] nums) {
            int n = nums.length;
            int ans = 0;;
            for (int a = 0; a < n; a++) {
                for (int b = a + 1; b < n; b++) {
                    for (int c = b + 1; c < n; c++) {
                        for (int d = c + 1; d < n; d++) {
                            if (nums[a] + nums[b] + nums[c] == nums[d]) {
                                ans++;
                            }
                        }
                    }
                }
            }
            return ans;
        }*/

        // 哈希
        public int countQuadruplets(int[] nums) {
            int n = nums.length;
            int ans = 0;
            Map<Integer, Integer> map = new HashMap<>();
            for (int b = n - 3; b >= 1; b--) {
                for (int d = b + 2; d < n; d++) {
                    map.put(nums[d] - nums[b + 1]
                            , map.getOrDefault(nums[d] - nums[b + 1], 0) + 1);
                }
                for (int a = 0; a < b; a++) {
                    ans += map.getOrDefault(nums[a] + nums[b], 0);
                }
            }
            return ans;
        }
    }
}
